The present invention relates to the field of Content Addressable Memory (CAM) and, more particularly, to a system for, and method of, implementing a RAM-Based Binary CAM and a RAM-Based Range Content Addressable Memory (RCAM).
Conventional memory arrays such as Random Access Memories (RAMs) store and retrieve data units indexed by their address.
Content Addressable Memories (CAMs) are associative memories that contain Key Entries and Associated Data Entries that uniquely correspond to the Key Entries. A CAM stores the key entries and the associated data entries at any available location and retrieves the Associated Data for any key that is submitted to be searched in the CAM.
A Binary CAM stores an ordered list of single integer key entries and a corresponding list of their associated data. An RCAM stores instead a list of key entries that represent range boundaries and a list of associated data that correspond uniquely to these ranges. A key search in a Binary CAM results in an exact match, whereas a key search in an RCAM matches an entire range. The RCAM also stores a list of associated boundary type entries that determine the validity of the corresponding ranges. This list can be stored in conjunction with the list of associated data or in a separate array.
A successful approach to utilizing RAM-based technology on a binary CAM is provided in my co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/00458, which is incorporated by reference for all purposes as if fully set forth herein. A method and apparatus are disclosed therein for the high-rate arrangement, storage and extraction of data in a two-dimensional memory array. The two-dimensional array, which consists of memory cells, is arranged in rows and columns, each of the key entries in these cells having a unique pair of indices that indicate the key entry location in the array. The associated data entries that correspond to these key entries are stored in another two-dimensional array under the same pair of indices. When a submitted key is searched and found, the associated data is retrieved from the corresponding cell in the other two-dimensional associated-data memory array and a match signal, xe2x80x9cTruexe2x80x9d or xe2x80x9cFalsexe2x80x9d, is also output with the retrieved associated data entry to indicate whether the associated data is valid or not. The key entries in the two-dimensional array are arranged, each entry in a separate cell, in rows or columns, in a subsequent ascending or descending order. The entries are arranged in the array so that at least a portion of the array is filled without blanks with valid entries. The arrays of the key entries and their associated data are kept in perfect sequence by Insert and Remove algorithms.
The main innovations introduced by this technology include:
Surrounding the RAM structure with search logic in the RAM periphery: The number of comparator units is proportional to the RAM periphery length rather than to the RAM area. This results in dramatic savings in the amount of comparator logic, while keeping the memory cell extremely efficient in density and speed. The CAM implementation overhead is typically less than 15%. Therefore, the CAM density obtained with this method is asymptotically close to the comparable size in RAM technology.
Fast Search Algorithm: The surrounding logic in conjunction with the RAM structure performs searches with the same throughput as a comparable RAM, and twice the latency. (Theoretically, single clock latency may be accomplished, but pipelining may yield a better throughput and a similar latency if measured on absolute time scale (nano-seconds).
Continuous xe2x80x9cHousekeepingxe2x80x9d Procedure: Unlike CAMs of the prior art, these CAM devices keep the xe2x80x9chouse in orderxe2x80x9d. That is, the deletion of keys does not leave xe2x80x9cholesxe2x80x9d in the list, which would otherwise require xe2x80x9chousekeepingxe2x80x9d operations on the managing processor section. Similarly, the addition of new keys keeps the list in a perfect sequence. This xe2x80x9chousekeepingxe2x80x9d procedure takes longer than the search, but is much faster than required by the system. The overhead associated with the Key List update is significantly shorter when compared with the time taken by the processor to do the housekeeping. This superior performance is due to the efficient RAM and Insert/Remove hardware architecture, which execute very time-efficient algorithms.
In my co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/00595, which is incorporated by reference for all purposes as if fully set forth herein, a method and apparatus are disclosed for arranging and storing a set of key entries and a corresponding set of associated data entries in storage areas within a memory device. Each location in the first storage area is assigned a unique index and is associated with the corresponding location to second storage area with the same index. Each key entry represents a range of consecutive values and is denoted herein as Range Key Entry. The range may be represented by its lower or upper boundary.
When a key is submitted for search and is found to belong to a range represented by a range key entry, the associated data entry with the same index is extracted from the memory as valid data and a Match signal is issued. If no range is found to contain the submitted key, no valid associated data is retrieved and a No-Match signal is issued.
A successful approach to utilizing RAM-based technology on an RCAM in a similar way that on a binary CAM is provided in my co-pending, unpublished (and as such, is not to be construed as prior art with regard to the present application) PCT Patent Application Serial No. IL01/01025, which is incorporated by reference for all purposes as if fully set forth herein. A method and apparatus are disclosed therein for the high-rate arrangement, storage of ranges of integers and extraction of data associated with these ranges in a two-dimensional memory array. The two-dimensional array, which consists of memory cells, is arranged in rows and columns, each of the key entries (representing range boundaries) in these cells having a unique pair of indices that indicate the key entry location in the array. The associated data entries that correspond uniquely to these ranges are stored in another two-dimensional array under the same pair of indices. When a submitted key is searched and found within an integer range, the associated data is retrieved from the corresponding cell in the other two-dimensional associated-data memory array.
The RCAM includes a third two-dimensional array, consisting of associated boundary type entries that also correspond uniquely to these ranges and are stored under the same pair of indices; these entries determine the validity of the corresponding ranges. A match signal, xe2x80x9cTruexe2x80x9d or xe2x80x9cFalsexe2x80x9d, is output accordingly with the retrieved associated data entry to indicate whether the matched range and the associated data are valid or not. The array of associated boundary type entries can be stored in conjunction with that of associated data entries or separately.
The key entries in the two-dimensional array are arranged, each entry in a separate cell, in rows or columns, in a subsequent ascending or descending order. The entries are arranged in the array so that at least a portion of the array is filled without blanks with valid entries.
In many cases, the relatively slow speed of the Insert and Remove operations hampers the performance of the system. It would, therefore, be highly advantageous to have a system for, and a method of significantly improving the speed of the Insert and Remove algorithms, while maintaining the arrays of the key entries and their associated data in perfect sequence.
The present invention relates to a device for binary CAMs and for RCAMs having multiple module content addressable memories, and a method of utilizing the device.
According to the teachings of the present invention there is provided, a method for arranging and storing data in a memory and for extracting the data from the memory in response to an input key, the method including the steps of: (a) providing a device including: (i) a memory having a plurality of module pairs, each of the module pairs having: (A) a key module including a first array of cells, the first array having at least two dimensions and having rows and columns, the first array containing a plurality of keys, each of the cells having a unique address and being accessible via an input key, the keys being arranged in monotonic order, and (B) an associated data module including a second array of cells, the second array having at least two dimensions and having rows and columns, the second array having a plurality of data entries, associated with the keys, wherein the memory is designed and configured such that each of the data entries is associated with a particular one of the keys, and (ii) processing means, and (b) performing a processing operation, using the processing means on each key module in parallel.
According to yet another aspect of the present invention there is provided a multiple module device for storing arranged data in a memory, and for extracting the data therefrom, the device including: (a) a memory having a plurality of module pairs, each of the module pairs having: (i) a key module including a first array of cells, the first array having at least two dimensions and having rows and columns, the first array containing a plurality of keys, each of the cells having a unique address and being accessible via an input key, the keys within each of the key modules being arranged in monotonic order, and (ii) an associated data module including a second array of cells, the second array having at least two dimensions and having rows and columns, the second array having a plurality of data entries, associated with the keys, wherein the memory is designed and configured such that each of the data entries is associated with a particular one of the keys, and (b) processing means designed and configured to search, in response to the input key, the plurality of keys within each key module, so as to identify a match.
According to further features in the described preferred embodiments, the keys within each key module define a module value span, and the first modules are arranged in monotonic order with respect to each module value span.
According to still further features in the described preferred embodiments, the multiple module device further includes: (c) sorting means for arranging the keys in monotonic order within the first array.
According to still further features in the described preferred embodiments, the memory includes a memory selected from the group of memories consisting of: SRAM, DRAM, CCD, ROM, EPROM, E2PROM, Flash-memory, and Magnetic-media.
According to still further features in the described preferred embodiments, the memory is a random access memory (RAM).
According to still further features in the described preferred embodiments, each of the associated data entries has a unique pair of row and column indices for association with a unique pair of row and column indices of a particular one of the keys.
According to still further features in the described preferred embodiments, the keys represent range boundary information.
According to still further features in the described preferred embodiments, the multiple module device further includes range validity information for each of the range boundary information, the range validity information stored within the memory.
According to still further features in the described preferred embodiments, the range boundary information is a single range-boundary value.
According to still further features in the described preferred embodiments, the range validity information is disposed in the first array, each range validity information corresponding to a particular single range-boundary value.
According to still further features in the described preferred embodiments, the range validity information is stored in a separate array.
According to still further features in the described preferred embodiments, the range validity information is disposed in the second array, each range validity information corresponding to a particular one of the associated data entries.
According to still further features in the described preferred embodiments, each key module includes a first register for holding a first key and a second register for holding a last key, the first key and the last key representing extreme values of the module value span, wherein the first register and the second register are designed and configured to produce register output signals.
According to still further features in the described preferred embodiments, each key module includes at least one comparator for comparing an index of a key having an extreme value of the module value span with an index of a key disposed in a last position of the key module.
According to still further features in the described preferred embodiments, the processing means include: i) a row locator containing at least a first comparator, for comparing contents of an end column of the first array with the input key.
According to still further features in the described preferred embodiments, the processing means further include: ii) a column locator containing at least a second comparator, for comparing contents of the row with the input key.
According to still further features in the described preferred embodiments, each of the module pairs further includes: (iii) a tristate buffer operatively connected to the key module and to the associated data module.
According to still further features in the described preferred embodiments, each of the module pairs further includes an associated boundary type module.
According to still further features in the described preferred embodiments, the associated boundary type module is operatively connected to a tristate buffer.
According to still further features in the described preferred embodiments, the output of the tristate buffer is enabled by a match signal received from the key module.
According to still further features in the described preferred embodiments, the device further includes an associated boundary type module including a third array of cells, the third array having at least two dimensions, and a plurality of data entries containing range validity information, each of the data entries associated with a particular one of the keys.
According to still further features in the described preferred embodiments, the processing operation includes a Search operation.
According to still further features in the described preferred embodiments, the processing operation includes an Insert operation.
According to still further features in the described preferred embodiments, the processing operation includes a Remove operation.
According to still further features in the described preferred embodiments, the processing operation includes an Update operation.
According to still further features in the described preferred embodiments, the processing operation includes a comparing operation.
According to still further features in the described preferred embodiments, the plurality of keys includes range boundary information, and the comparing operation includes comparing a value of the input key with the range boundary information to determine a particular range to which the input key belongs.
According to still further features in the described preferred embodiments, a row or column containing the range boundary information is selected by the following steps: (i) performing a comparison between the range boundary information and the input key to produce a result, and (ii) identifying a row or column in which the result undergoes a change in inequality status.
According to still further features in the described preferred embodiments, the method further includes the step of: (iii) selecting the row or column.
According to still further features in the described preferred embodiments, the method further includes the steps of: (c) identifying within a particular key module, a row into which a new key should be inserted and selecting the row, and (d) inserting the new key into an insertion location in the particular key module while maintaining the monotonic order within each of the key modules.
According to still further features in the described preferred embodiments, the identifying in step (c) includes a comparison of the new key with at least one end key of the plurality of keys, the end key disposed in an end column in the particular key module.
According to still further features in the described preferred embodiments, the identifying in step (c) includes examining all the key modules in parallel.
According to still further features in the described preferred embodiments, the method further includes the step of: (e) checking, before step (d), that the particular key module is devoid of a key of identical value to the new key.
According to still further features in the described preferred embodiments, the method further includes the step of: (e) identifying a column index for the new range boundary value by performing a comparison of the new range boundary value with the range boundary information disposed in the row.
According to still further features in the described preferred embodiments, the maintaining of the monotonic order is achieved by shifting a content of each cell disposed after the insertion location respectively, by one position, thereby completely filling at least a portion of the first array with the keys.
According to still further features in the described preferred embodiments, the data associated with the new key is inserted into the associated data module of the module pair containing the particular key module.
According to still further features in the described preferred embodiments, the method further includes the steps of: (c) identifying within a particular key module of the key modules, a row containing a key for removing, and selecting the row, and (d) removing the requisite key from a removal location in the particular key module while maintaining monotonic order within each of the key modules.
According to still further features in the described preferred embodiments, the method further includes the steps of: (c) identifying within a particular key module, a key that needs to be removed, and selecting the row, and (d) removing this key from a removal location in the particular key module while maintaining monotonic order within each of the key modules.